public class prog {
    public static void main(String[] args) {
        System.out.println();
    }
}
class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int n=timeSeries.length;
        int count=0;
        if(n==0){
            return 0;
        }
        for(int i=0;i<n-1;i++){
            count+=Math.min(timeSeries[i+1]-timeSeries[i],duration);
        }
        return count+duration;
    }
}








class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max=0;
        int count=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==1){
                count++;
            }else {
                count=0;
            }
            max=Math.max(max,count);
        }
        return max;
    }
}









class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int leng=g.length;
        int lens=s.length;
        int count=0;
        for(int i=0,j=0;i<leng&&j<lens;i++,j++){
            while(j<lens&&g[i]>s[j]){
                j++;
            }
            if(j<lens){
                count++;
            }
        }
        return count;
    }
}









class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int count=0;
        for(int i=1;i<nums.length;i++){
            count+=nums[i]-nums[0];
        }
        return count;
    }
}









class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n=nums.length;
        List<Integer> ret=new ArrayList<>();
        for(int num : nums){
            int x=(num-1)%n;
            nums[x]+=n;
        }
        for(int i=0;i<n;i++){
            if(nums[i]<=n){
                ret.add(i+1);
            }
        }
        return ret;
    }
}










/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head=null;
        for(ListNode y : lists){
            head=merge(head,y);
        }
        return head;
    }
    public ListNode merge(ListNode x,ListNode y){
        ListNode head=new ListNode(-1);
        ListNode cur=head;
        while(x!=null&&y!=null){
            if(x.val<y.val){
                cur.next=x;
                x=x.next;
            }else{
                cur.next=y;
                y=y.next;
            }
            cur=cur.next;
        }
        if(x!=null){
            cur.next=x;
        }
        if(y!=null){
            cur.next=y;
        }
        return head.next;
    }
}














/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head=null;
        for(ListNode x : lists){
            head=mergekList(head,x);
        }
        return head;
    }
    public ListNode mergekList(ListNode y,ListNode x){
        ListNode newhead=new ListNode(-1);
        ListNode cur=newhead;
        while(y!=null&&x!=null){
            if(y.val<x.val){
                cur.next=y;
                y=y.next;
            }else{
                cur.next=x;
                x=x.next;
            }
            cur=cur.next;
        }
        if(y!=null){
            cur.next=y;
        }
        if(x!=null){
            cur.next=x;
        }
        return newhead.next;
    }
}











class Solution {
    public boolean isSubsequence(String s, String t) {
        int lens=s.length();
        int lent=t.length();
        int i=0,j=0;
        while(i<lens&&j<lent){
            if(s.charAt(i)==t.charAt(j)){
                i++;
            }
            j++;
        }
        return i==lens;
    }
}









class Solution {
    public String toHex(int num) {
        if(num==0){
            return "0";
        }
        char[] str=new char[]{'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        StringBuffer sb=new StringBuffer();
        int sum=0;
        while(num!=0){
            sum=num&15;
            sb.insert(0,str[sum]);
            num>>>=4;
        }
        return sb.toString();
    }
}









class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> str=new ArrayList<>();
        for(int i=1;i<=n;i++){
            if(i%3==0&&i%5==0){
                str.add("FizzBuzz");
            }else if(i%3==0){
                str.add("Fizz");
            }else if(i%5==0){
                str.add("Buzz");
            }else{
                str.add(Integer.toString(i));
            }
        }
        return str;
    }
}










class Solution {
    public int longestPalindrome(String s) {
        int[] count =new int[128];
        int len=s.length();
        for(int i=0;i<len;i++){
            char ch=s.charAt(i);
            count[ch]++;
        }
        int sum=0;
        for(int x : count){
            sum+=x/2*2;
            if(sum%2==0&&x%2==1){
                sum++;
            }
        }
        return sum;
    }
}









class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder res=new StringBuilder();
        int len1=num1.length()-1;
        int len2=num2.length()-1;
        int count=0;
        int sum=0;
        while(len1>=0||len2>=0){
            int n1=len1>=0?num1.charAt(len1)-'0':0;
            int n2=len2>=0?num2.charAt(len2)-'0':0;
            count=n1+n2+sum;
            sum=count/10;
            int tmp=count%10;
            res.append(tmp);
            len1--;
            len2--;
        }
        if(sum>0){
            res.append(sum);
        }
        return res.reverse().toString();
    }
}











class Solution {
    public int thirdMax(int[] nums) {
        Arrays.sort(nums);
        int count=1;
        for(int i=nums.length-1;i>0;i--){
            if(nums[i-1]!=nums[i]){
                count++;
            }
            if(count==3){
                return nums[i-1];
            }
        }
        return nums[nums.length-1];
    }
}









class Solution {
    public int countSegments(String s) {
        int count=0;
        String[] str=s.split(" ");
        for(String x : str){
            if(!x.equals("")){
                count++;
            }
        }
        return count;
    }
}










class Solution {
    public String reverseVowels(String s) {
        int len=s.length();
        char[] arr=s.toCharArray();
        int i=0;
        int j=len-1;
        while(i<j){
            while(i<len&&!isVowel(arr[i])){
                i++;
            }
            while(j>0&&!isVowel(arr[j])){
                j--;
            }
            if(i<j){
                swap(arr,i,j);
                i++;
                j--;
            }
        }
        return new String(arr);

    }
    public boolean isVowel(char arr){
        return "aeiouAEIOU".indexOf(arr)>=0;
    }
    public void swap(char[] arr,int i,int j){
        char ch=arr[i];
        arr[i]=arr[j];
        arr[j]=ch;
    }
}











class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] str=s.split(" ");
        if(pattern.length()!=str.length){
            return false;
        }
        Map<Object,Integer> map=new HashMap<>();
        for(Integer i=0;i<str.length;i++){
            if(map.put(pattern.charAt(i),i)!=map.put((str[i]),i)){
                return false;
            }
        }
        return true;
    }
}










class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int len1=nums1.length;
        int len2=nums2.length;
        int[] arr=new int [Math.min(len1,len2)];
        int i=0;
        int j=0;
        int k=0;
        while(i<len1&&j<len2){
            if(nums1[i]<nums2[j]){
                i++;
            }else if(nums2[j]<nums1[i]){
                j++;
            }else{
                arr[k]=nums1[i];
                k++;
                i++;
                j++;
            }
        }
        return Arrays.copyOfRange(arr,0,k);
    }
}












class Solution {
    public int firstUniqChar(String s) {
        int[] arr=new int[26];
        int len=s.length();
        for(int i=0;i<len;i++){
            arr[s.charAt(i)-'a']++;
        }
        for(int i=0;i<len;i++){
            if(arr[s.charAt(i)-'a']==1){
                return  i;
            }
        }
        return -1;
    }
}










class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] arr=new int[26];
        for(char ch : magazine.toCharArray() ){
            arr[ch-'a']++;
        }
        for(char ch : ransomNote.toCharArray()){
            arr[ch-'a']--;
        }
        for(int num : arr){
            if(num<0){
                return false;
            }
        }
        return true;
    }
}














class NumArray {
    int[] sum;
    public NumArray(int[] nums) {
        int len=nums.length;
        sum=new int[len];
        for(int i=0;i<len;i++){
            sum[i]=nums[i];
        }
    }

    public int sumRange(int left, int right) {
        int count=0;
        for(int i=left;i<=right;i++){
            count+=sum[i];
        }
        return count;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */











class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res=new ArrayList<>();
        int i=0;
        for(int j=0;j<nums.length;j++){
            if(nums.length==j+1||nums[j]+1!=nums[j+1]){
                StringBuilder sb=new StringBuilder();
                sb.append(nums[i]);
                if(i!=j){
                    sb.append("->").append(nums[j]);
                }
                res.add(sb.toString());
                i=j+1;
            }
        }
        return res;
    }
}









class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            if(set.contains(nums[i])){
                return true;
            }
            set.add(nums[i]);
            if(set.size()>k){
                set.remove(nums[i-k]);
            }
        }
        return false;
    }
}











class Solution {
    public int titleToNumber(String columnTitle) {
        int num=0;
        int count=1;
        for(int i=columnTitle.length()-1;i>=0;i--){
            int tmp=columnTitle.charAt(i)-'A'+1;
            num+=tmp*count;
            count*=26;
        }
        return num;
    }
}





class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuffer sb=new StringBuffer();
        while(columnNumber!=0){
            columnNumber--;
            sb.append((char)(columnNumber%26+'A'));
            columnNumber/=26;
        }
        return sb.reverse().toString();
    }
}